package swordRefersOffer.p38;

import java.util.*;

/**
 * 字符串排列
 * @author: trtan
 * @date: 2021-06-22 17:22
 **/
public class ArrangementOfStrings {
    public String[] permutation(String s) {
        char[] arr = s.toCharArray();
        boolean[] vis = new boolean[arr.length];
        Arrays.fill(vis, false);
        Set<String> set = new HashSet<>();
        dfs(set, arr, vis, "", 0);
        String[] result = new String[set.size()];
        int i = 0;
        for (Iterator<String> it = set.iterator(); it.hasNext();) {
            result[i++] = it.next();
        }
        return result;
    }

    void dfs(Set<String> set, char[] arr, boolean[] vis, String s, int num) {
        if (num == arr.length) {
            set.add(s);
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (!vis[i]) {
                vis[i] = true;
                dfs(set, arr, vis, s + arr[i], num + 1);
                vis[i] = false;
            }
        }
    }
}
